class Solution
{
public:
    // https://leetcode.cn/problems/count-and-say/
    string countAndSay(int n) // 递归
    {
        if (n == 1)
            return "1";
        string str = countAndSay(n - 1);
        char a = str[0];
        int count = 0;
        string st;
        for (auto &c : str)
        {
            if (c == a)
                count++;
            else
            {
                st += to_string(count) + a;
                a = c;
                count = 1;
            }
        }
        st += to_string(count) + a;
        return st;
    }

    // 循环模拟
    string countAndSay1(int n)
    {
        string ret = "1";
        for (int j = 1; j < n; j++)
        {
            string str;
            int len = ret.size();
            for (int left = 0, right = 0; right < len;)
            {
                while (right < len && ret[left] == ret[right])
                    right++;
                str += to_string(right - left) + ret[left];
                left = right;
            }
            ret = str;
        }
        return ret;
    }

    // https://leetcode.cn/problems/minimum-number-of-frogs-croaking/
    int minNumberOfFrogs(string croakOfFrogs)
    {
        unordered_map<char, int> ci;
        string str = "croak";
        int add[5] = {0};
        for (int i = 0; i < str.size(); i++)
        {
            ci[str[i]] = i;
        }
        for (int i = 0; i < croakOfFrogs.size(); i++)
        {
            char c = croakOfFrogs[i];
            if (!ci.count(c))
                return -1;
            if (add[(ci[c] + 4) % 5] > 0)
                add[(ci[c] + 4) % 5]--;
            else if (c != 'c')
                return -1;
            add[ci[c]]++;
        }
        for (int i = 0; i < 4; i++)
        {
            if (add[i] > 0)
                return -1;
        }
        return add[4];
    }

    //效率更高写法
    int minNumberOfFrogs1(string croakOfFrogs)
    {
        int n = croakOfFrogs.size(), ans = 0;
        int c = 0, r = 0, o = 0, a = 0, k = 0;
        for (int i = 0; i < n; i++)
        {
            if (croakOfFrogs[i] == 'c') c++;
            if (croakOfFrogs[i] == 'r') r++;
            if (croakOfFrogs[i] == 'o') o++;
            if (croakOfFrogs[i] == 'a') a++;
            if (croakOfFrogs[i] == 'k') k++;
            if (!(c >= r && r >= o && o >= a && a >= k)) return -1;
            ans = max(ans, c - k);
        }
        return c == r && r == o && o == a && a == k ? ans : -1;
    }

    //https://leetcode.cn/problems/sort-colors/
    void sortColors(vector<int>& nums) 
    {
        int left = -1, right = nums.size(), i = 0;
        while(i < right)
        {
            if(nums[i] == 0) swap(nums[i++], nums[++left]);
            else if(nums[i] == 1) i++;
            else swap(nums[--right], nums[i]);
        }
    }
};